package com.lihepeng.leecode.solid_aim_offer.tree;

/**
 * 描述
 * 给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。
 * 1.返回第k小的节点值即可
 * 2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1
 * 3.保证n个节点的值不一样
 *
 *
 * 数据范围： 0 \le n \le10000≤n≤1000，0 \le k \le10000≤k≤1000，树上每个结点的值满足0 \le val \le 10000≤val≤1000
 * 进阶：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
 */
public class Solution54 {
    /**
     * 二叉树遍历
     * @param proot
     * @param k
     * @return
     */
    private int count =0;
    private TreeNode treeNode = null;
    public int KthNode (TreeNode proot, int k) {
        minOrder(proot,k);
        if (treeNode!=null) {
            return treeNode.val;
        }else {
            return -1;
        }
    }
    public void minOrder( TreeNode proot, int k){
        if (proot ==null || count >k){
            return;
        }
        minOrder(proot.left,k);
        if (++count == k) {
            treeNode = proot;
        }
        minOrder(proot.right,k);

    }
}
